package lhc.alg.top100;

/**
 * description: 买股票买股票
 *
 * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
 *
 * 原始的状态转移方程，没有可化简的地方
 * dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
 * dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
 *
 * 处理base case
 *
 * if(i-1 == -1){
 * dp[i][k][0] = 0;
 * dp[i][k][1] = - prices[i];
 * continue;
 * }
 *
 * labuladong挺好使 无脑买卖股票
 *
 * author: hongchen.liao
 * date:  2022/7/26
 */
public class _123_Buy_and_sell_stocks_3 {

    //dp解法
    class Solution {
        public int maxProfit(int[] prices) {
            int max_k = 2;
            int n = prices.length;
            int[][][] dp = new int[n][max_k+1][2];
            for(int i = 0; i < n; i++){
                for(int k = max_k; k >= 1; k--){
                    //处理base case
                    if(i - 1 == -1){
                        dp[i][k][0] = 0;
                        dp[i][k][1] = -prices[i];
                        continue;
                    }
                    dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1]+prices[i]);
                    dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i]);
                }
            }
            return dp[n-1][max_k][0];
        }
    }

    //dp状态机 k=2直接穷举出来 猛的一批
    class Solution2 {
        public int maxProfit(int[] prices) {
            int dp_i10 = 0, dp_i11 = Integer.MIN_VALUE;
            int dp_i20 = 0, dp_i21 = Integer.MIN_VALUE;
            for(int price : prices){
                dp_i10 = Math.max(dp_i10, dp_i11 + price);
                dp_i11 = Math.max(dp_i11, -price);

                dp_i20 = Math.max(dp_i20, dp_i21 + price);
                dp_i21 = Math.max(dp_i21, dp_i10 - price);
            }
            return dp_i20;
        }
    }


}
